/*********************************************************************************
  *Copyright (c)    2021   xldeng
  *FileName:        416.cpp.c
  *Author:          xldeng
  *Version:         1.0
  *Date:            2021/2/12 21:17
  *Description:     
  *Others:          
  *Function List:   
     1.…………
  *History:  
     1.Date:
       Author:
       Modification:
**********************************************************************************/
//给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
//
//注意:
//
//每个数组中的元素不会超过 100
//数组的大小不会超过 200

#include "../header.h"

class Solution {
public:
    bool canPartition(vector<int> &nums) {
        int sum = 0;
        for (auto item:nums)
            sum += item;
        if (sum % 2 != 0)
            return false;
        int n = nums.size();
        sum /= 2;
//        // dp 前i个数能否凑到j
//        vector<vector<bool>> dp(n + 1, vector<bool>(sum + 1, false));
//        // 初始化
//        for (int i = 0; i <= n; ++i)
//            dp[i][0] = false;
//        for (int i = 1; i <= n; ++i)
//            for (int j = 1; j <= sum; ++j)
//                if (j - nums[i - 1] < 0)
//                    dp[i][j] = dp[i-1][j];
//                else
//                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
//        return dp[n][sum];
        vector<bool> dp(sum + 1, false);
        dp[0] = true;
        for (int i = 0; i < n; ++i) {
            for (int j = sum; j >= 1; --j) {
                if (j >= nums[i])
                    dp[j] = dp[j] || dp[j - nums[i]];
            }
        }
        return dp[sum];
    }
};
